package com.ln.prac.base.m202206.d14;

import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;

/**
 * <pre>
 *  排序相关
 * </pre>
 *
 * @Author zhangj
 * @Date 2022/6/14 21:47
 */
public class SortTest {

//    public static List<Integer> fastSort(List<Integer> list) {
//        if(list.size() <= 1) {
//            return list;
//        }
//
//        // 取第一个数字，小于它的整理到左边，大于它的整理到右边去
//        int num = list.get(0);
//
//        var left = list.stream().filter(x->x < num).collect(Collectors.toList());
//        var middle = list.stream().filter(x->x == num).collect(Collectors.toList());
//        var right = list.stream().filter(x->x > num).collect(Collectors.toList());
//
//        // 递归下去
//        left = fastSort(left);
//        right = fastSort(right);
//
//        // 合并
//        left.addAll(middle);
//        left.addAll(right);
//
//        return left;
//    }


    public static void fastSort2(Integer[] A) {
        fastSort2(A, 0, A.length);
    }

    public static void fastSort2(Integer[] A, int l, int r) {
        if(r - l <= 1) {
            return;
        }

        // 找到中间的下标
        int i = partition(A, l, r);

        // 递归下去
        fastSort2(A, l, i);
        fastSort2(A, i + 1, r);

        // 合并
        mergeSort(A, l, i, r);

    }

    private static void mergeSort(Integer[] A, int l, int mid, int r) {
        Integer[] B = Arrays.copyOfRange(A, l, mid + 1);
        Integer[] C = Arrays.copyOfRange(A, mid, r + 1);

        B[B.length - 1] = C[C.length - 1] = Integer.MAX_VALUE;
        int i = 0, j = 0;
        for (int k = l; k < r; k++) {
            if(B[i] < C[j]) {
                A[k] = B[i++];
            } else {
                A[k] = C[j++];
            }
        }


    }

    private static int partition(Integer[] A, int l, int r) {
        int x = A[l];
        int i = l + 1;
        int j = r;

        // x | -- left --| -- middle -- | -- right -- |
        while (i != j) {
            if(A[i] < x) {
                ++i;
            } else {
                swap(A, i, --j);
            }
        }

        swap(A, i - 1, l);
        return i - 1;
    }

    private static void swap(Integer[] A, int i, int j) {
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }

    /**
     * 插入排序 ； 类似抓牌过程，从牌堆到手牌
     * @param A
     */
    public static void insertSort(Integer[] A) {
        for (int i = 1; i < A.length; i++) {
            int tmp = A[i];
            int j = i;
            for (; j > 0 && A[j - 1] > tmp; j--) {
                A[j] = A[j - 1];
            }
            A[j] = tmp;
        }
    }


//    public static void main(String[] args) {
//        var arr = new Integer[30];
//
//        var random = new Random();
//        for (int i = 0; i < 30; i++) {
//            arr[i] = random.nextInt(1000);
//        }
//
//        System.out.println(Arrays.asList(arr));
//
////        System.out.println(fastSort(Arrays.asList(arr)));
////        fastSort2(arr);
//        insertSort(arr);
//        System.out.println(Arrays.asList(arr));
//
//
//    }

}
